package com.leecode.xiehf.page_02;

import com.leecode.Printer;

/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0064 extends Printer {

    public static void main(String[] args) {
        Solution_0064 solution = new Solution_0064();
        int s = solution.minPathSum(new int[][]{
                {0, 1, 0,},
                {0, 1, 0,},
                {0, 0, 0,}
        });
        print(s);
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int column = 1; column < n; column++ ) {
            dp[0][column] = grid[0][column] + dp[0][column - 1];
        }
        for(int row = 1; row < m; row++) {
            dp[row][0] = grid[row][0] + dp[row - 1][0];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
            }
        }
        return dp[m- 1][n - 1];
    }
}
